﻿namespace Leetcode.N0386;

public class Solution
{
    public IList<int> LexicalOrder(int n)
    {
        int levelCount = 0;
        int k = n;
        while (k > 0)
        {
            levelCount++;
            k /= 10;
        }

        var curLevel = 0;
        var levelDight = new int[levelCount];
        var levelVal = new int[levelCount];

        var result = new List<int>();
        levelVal[0] = 1;

        for (int i = 0; i < n; i++)
        {
            var val = levelVal[curLevel] + levelDight[curLevel];
            result.Add(val);

            // 如果不是最后一位，向后移动一位，否则当前的位数字 +1
            if (curLevel < levelCount - 1 && val * 10 <= n)
            {
                curLevel++;
                levelVal[curLevel] = val * 10;
                levelDight[curLevel] = 0;
            }
            else
            {
                levelDight[curLevel]++;
            }

            // 如果是最后一位数字或者值已经超过了最大值，向前移动
            if (curLevel > 0 && (val >= n || levelDight[curLevel] == 10))
            {
                levelDight[curLevel] = 0;
                curLevel--;

                levelDight[curLevel]++;
                while (levelDight[curLevel] == 10)
                {
                    levelDight[curLevel] = 0;
                    curLevel--;
                    levelDight[curLevel]++;
                }
            }
        }

        return result;
    }
}
